package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC600 {


    /**
     * 此题目参考了已有经验
     */
    public int findIntegers(int num) {
        int[] fib = new int[31];
        fib[0] = 1;
        fib[1] = 2;
        for (int i = 2; i < 31; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        int k = 31, res = 0;
        boolean pre = false;
        while (k >= 0) {
            if ((num & (1 << k)) == (1 << k)) {//bit k is 1
                res += fib[k];
                if (pre) {
                    return res;
                }
                pre = true;
            } else {//bit k is 0
                pre = false;
            }
            --k;
        }

        return res + 1;
    }

    public static void main(String[] args) {
        LC600 an = new LC600();
        System.out.println(an.findIntegers(5));

    }
}
